{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For today all data are distinct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class node:\n",
    "    def __init__(self,key=None):\n",
    "        self.key=key\n",
    "        self.next=None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "class linked_list:\n",
    "    def __init__(self):\n",
    "        self.head=node()\n",
    "\n",
    "    # Adds new node containing 'key' to the end of the linked list.\n",
    "    def append(self,key):\n",
    "        new_node=node(key)\n",
    "        cur=self.head\n",
    "        while cur.next!=None:\n",
    "            cur=cur.next\n",
    "        cur.next=new_node\n",
    "\n",
    "    # Returns the length (integer) of the linked list.\n",
    "    def length(self):\n",
    "        cur=self.head\n",
    "        total=0\n",
    "        while cur.next!=None:\n",
    "            total+=1\n",
    "            cur=cur.next\n",
    "        return total \n",
    "\n",
    "    # Prints out the linked list in traditional Python list format. \n",
    "    def display(self):\n",
    "        elems=[]\n",
    "        cur_node=self.head\n",
    "        while cur_node.next!=None:\n",
    "            cur_node=cur_node.next\n",
    "            elems.append(cur_node.key)\n",
    "        print(elems)\n",
    "\n",
    "    # Returns the value of the node at 'index'. \n",
    "    def get(self,index):\n",
    "        if index>=self.length() or index<0: # added 'index<0' post-video\n",
    "            print(\"ERROR: 'Get' Index out of range!\")\n",
    "            return None\n",
    "        cur_idx=0\n",
    "        cur_node=self.head\n",
    "        while True:\n",
    "            cur_node=cur_node.next\n",
    "            if cur_idx==index: return cur_node.key\n",
    "            cur_idx+=1\n",
    "\n",
    "    # Deletes the node at index 'index'.\n",
    "    def erase(self,index):\n",
    "        if index>=self.length() or index<0: \n",
    "            print(\"ERROR: 'Erase' Index out of range!\")\n",
    "            return \n",
    "        cur_idx=0\n",
    "        cur_node=self.head\n",
    "        while True:\n",
    "            last_node=cur_node\n",
    "            cur_node=cur_node.next\n",
    "            if cur_idx==index:\n",
    "                last_node.next=cur_node.next\n",
    "                return\n",
    "            cur_idx+=1\n",
    "\n",
    "    # Allows for bracket operator syntax (i.e. a[0] to return first item).\n",
    "    def __getitem__(self,index):\n",
    "        return self.get(index)\n",
    "\n",
    "\n",
    "    #######################################################\n",
    "\n",
    "    # Inserts a new node at index 'index' containing key 'key'.\n",
    "    # Indices begin at 0. If the provided index is greater than or \n",
    "    # equal to the length of the linked list the 'key' will be appended.\n",
    "    def insert(self,index,key):\n",
    "        if index>=self.length() or index<0:\n",
    "            return self.append(key)\n",
    "        cur_node=self.head\n",
    "        prior_node=self.head\n",
    "        cur_idx=0\n",
    "        while True:\n",
    "            cur_node=cur_node.next\n",
    "            if cur_idx==index: \n",
    "                new_node=node(key)\n",
    "                prior_node.next=new_node\n",
    "                new_node.next=cur_node\n",
    "                return\n",
    "            prior_node=cur_node\n",
    "            cur_idx+=1\n",
    "\n",
    "    # Inserts the node 'node' at index 'index'. Indices begin at 0.\n",
    "    # If the 'index' is greater than or equal to the length of the linked \n",
    "    # list the 'node' will be appended.\n",
    "    def insert_node(self,index,node):\n",
    "        if index<0:\n",
    "            print(\"ERROR: 'Erase' Index cannot be negative!\")\n",
    "            return\n",
    "        if index>=self.length(): # append the node\n",
    "            cur_node=self.head\n",
    "            while cur_node.next!=None:\n",
    "                cur_node=cur_node.next\n",
    "            cur_node.next=node\n",
    "            return\n",
    "        cur_node=self.head\n",
    "        prior_node=self.head\n",
    "        cur_idx=0\n",
    "        while True:\n",
    "            cur_node=cur_node.next\n",
    "            if cur_idx==index: \n",
    "                prior_node.next=node\n",
    "                return\n",
    "            prior_node=cur_node\n",
    "            cur_idx+=1\n",
    "\n",
    "    # Sets the key at index 'index' equal to 'key'.\n",
    "    # Indices begin at 0. If the 'index' is greater than or equal \n",
    "    # to the length of the linked list a warning will be printed \n",
    "    # to the user.\n",
    "    def set(self,index,key):\n",
    "        if index>=self.length() or index<0:\n",
    "            print(\"ERROR: 'Set' Index out of range!\")\n",
    "            return\n",
    "        cur_node=self.head\n",
    "        cur_idx=0\n",
    "        while True:\n",
    "            cur_node=cur_node.next\n",
    "            if cur_idx==index: \n",
    "                cur_node.key=key\n",
    "                return\n",
    "            cur_idx+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll=linked_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ll.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.head=node(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ll.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.insert(1,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.length()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.insert(2,9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.insert(2,18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.length()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.insert(3,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.append(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.display()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.length()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for i in range(ll.length()):\n",
    "    print(ll[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(ll.head.key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "ll.erase(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for i in range(ll.length()):\n",
    "    print(ll[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
